package com.linzm.leetcode.primary.数组.二分法;

import org.junit.Test;

/**
 * @Author zimingl
 * @Date 2022/10/6 14:52
 * @Description: TODO
 */
public class 数组69x的平方根 {

    private static int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = (int) Math.exp(0.5 * Math.log(x));
        return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
    }

    @Test
    public void test01() {
        int x = 8;
        System.out.println(mySqrt(8));
    }

    private static int mySqrt2(int x) {
        // [0, x] mid * mid
        int left = 0;
        int right = x;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (x >= (long) mid * mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left - 1;
    }

    @Test
    public void test02() {
        int x = 8;
        System.out.println(mySqrt2(8));
    }
}
